This invention relates to the field of computer graphics. More specifically the invention relates to the simplification of geometric models for the purpose of display.
In the field of mechanical computer aided design (MCAD), geometric models are sometimes simultaneously represented by wire-frame and surface descriptions. For example, a model may be displayed by using a surface description to render the surface and a wire-frame description to show sharp edges, as in FIG. 2. The simultaneous use of surface and wire-frame descriptions of geometric models is also used for display purposes in other fields in MCAD. One such field is the application of numerical analysis to geometric models.
Numerical methods are frequently used to simulate the response of geometric models to a diverse variety of imposed environments. In one popular numerical method known as the finite element method, geometric models are represented by an assembly of subdivisions called finite elements. Finite elements are interconnected at point locations called nodes. Within a finite element, the value of a dependent variable is completely determined by the value of the dependent variable at nodes of the element. The use of the finite element method to simulate real-world problems is commonly referred to as finite element analysis. An assembly of finite elements is referred to as a finite element mesh. The finite element mesh serves as an alternate representation of the original real or abstract geometric model.
It is common practice to use graphical representations of the finite element mesh and one or more computed results to examine a solution obtained from a finite element analysis. For finite element meshes composed of 2-dimensional or 3-dimensional elements embedded in the 3-dimensional Euclidean space, graphical representations can be used to simultaneously communicate the structure of the finite element mesh, the surface of the finite element mesh (or geometric model) and the scalar magnitude of a solution component. Here polygons (usually triangles) are used to represent the surface of the mesh, line segments are used to represent the boundaries of individual elements, and color is used to represent the scalar magnitude of the solution component (e.g., temperature). Typically, the graphical result is obtained by combining a surface rendering with a line segment rendering. The surface rendering is used to represent the mesh surface and a scalar magnitude either representing or derived from a solution component. The shading is performed by applying shading algorithms. These shading algorithms use as input the geometry of the mesh surface and the color derived from the scalar magnitude of the solution component. The line segment rendering is generated from the edges of individual finite elements in the finite element mesh. The scalar magnitude of the solution component is frequently represented by a single color selected from a banded color map. The banded color map represents a contiguous range of scalar values with a single color. The final rendering usually takes one of two forms. One rendering mode, referred to as the iso mode, is used to represent scalar values attached to nodes and intra-finite element transitions from a color representing one scalar value to a color representing another scalar value. The other rendering mode, referred to as the finge mode, is used to represent scalar values attached to 2-dimensional faces in the mesh. The fringe mode uses one color corresponding to the scalar value to represent the face.
Most of the existing techniques for visualizing surface descriptions of the geometric models utilize triangle meshes. The geometry of a triangle mesh refers to the pair (K, V), where K is a simplicial complex of degree 2 specifying the connectivity of the mesh simplices, and V={v1, . . . , vm} is the set of vertex positions vi=(xi, yi, zi) defining the shape of the mesh in R3. In the FEM applications, there are either discrete scalar attributes D associated with the faces of the mesh, or scalar attributes S associated with the vertices of the mesh. In the FEM analysis, model descriptions also involve a wire-frame description of a geometric model (finite element mesh). A wire-frame description is represented by a subcomplex L⊂K, where L is a degree 1 subcomplex of K. The visualization task is to render either the triple (N, L, V) or one of the quadruples K, L, V, D) (for the fringe rendering mode) or K, L, V, S) (for the iso rendering mode). For example, FIG. 2 is a visualization of some triple (K, L, V).
The graphical detail contained in a visualization is not always required for display. Furthermore, graphical detail may be reduced to increase the display rate by decreasing the required graphics processing. A variety of simplification techniques aimed at reducing the amount of graphics processing and increasing display rates by sacrificing geometric detail have been covered in the literature (see, for example, Garland and Heckbert, xe2x80x9cSurvey of Polygonal Surface Simplification Algorithmsxe2x80x9d, Multiresolution Surface Modeling Course, SIGGRAPH-97). These simplification reduce the graphics processing to increase the frame rates by rendering representations containing lower levels of geometric detail than the original geometric model. Factors such as the size in screen space of the rendered model distance from the viewer, relative importance of the model requested frame rate, relative motion between the viewer and the model, are used to select a simplified representation of the original model. All of these techniques attempt to produce a simplified model that, when rendered, retains as much image fidelity as possible with a rendering of the original model.
There exist several techniques that address the simplification of meshes. In most approaches, the initial meshes are replaced by approximations with fewer faces which produce visually similar results, thereby improving rendering efficiency. Rossignac and Borrel (xe2x80x9cMulti-resolution 3D approximations for rendering complex scenesxe2x80x9d, Modeling in Computer Graphics, 455-465 (Springer-Verlag 1993) and U.S. Pat. No. 5,448,686) proposed one of the earliest simplification algorithms. Their algorithm divides the model into cells of a uniform rectangular grid, and replaces all vertices within the grid cell by a single representative vertex.
The edge collapse operation has been used extensively in simplification, and it generally produces higher quality results. Garland and Heckbert (xe2x80x9cSurface simplification using quadric error metricsxe2x80x9d, Computer Graphics Proceedings, Animal Conference Series, 1997, 209-216) maintain a 4 by 4 symmetric matrix at each vertex that allows to track square distances to the faces of the original model. They subsequently generalized the quadric error metric to support simplification of surfaces with color and texture (xe2x80x9cSimplifyng surfaces with color and texture using quadric error metricsxe2x80x9d, IEEE Visualization ""98 Proceedings, October 1998, 263-269). Lindstrom and Turk (xe2x80x9cFast and memory efficient polygonal simplificationxe2x80x9d, IEEE Visualization ""98 Proceedings, October 1998, 279-286) determine the vertex placement by minimizing the quadratic volume, boundary, and triangle shape objective functions, with the cost of edge collapse determined by the volume and boundary functions. Lindstrom (xe2x80x9cOut-of-core simplification of large polygonal modelsxe2x80x9d, Computer Graphics Proceedings, Annual Conference Series, 2000, 259-262) has proposed a method extending the vertex clustering scheme of Rossignac and Borrel by using quadric error metrics to select the representative vertex for each cell in the uniform grid.
Standard techniques exist to simultaneously display wire-frame and surface descriptions of geometric models. However, as the complexity of the geometric model increases, the number of polygons and line segments that need to be rendered to convey the surface description and the wire-frame description grows, and it becomes increasingly difficult for the computer to render the visualization at the rates required for interactive inspection (3 Hz-30 Hz). It is obvious to use prior art techniques from geometric simplification to address the simplification of surface descriptions to increase interactive frame rates. Standard techniques also exist to simplify surface descriptions of geometric models while preserving certain edges. However, there are no prior art techniques which use a simplified surface description of a geometric model to simplify the wire-frame description of the model. Furthermore, prior art does not consider the problem of using computational results attached to a the geometric model to guide the simplification process when viewing results using the fringe mode of display.
An object of this invention is a system and method for the accelerated rendering of surface and wire-frame descriptions of a geometric model by using a simplification of the surface description to guide the simplification of the wire-frame description.
An object of this invention is a method to use the results obtained from a finite element analysis to guide the simplification of a surface.
The present invention is a system for simplifying a geometric model to accelerate the rendering of the geometric model. A surface description of the geometric model is stored in one or more of the system memories. A wire-frame description of the geometric model is also stored. A surface simplification process alters the surface description to create an approximation of the original surface description. A wire-frame draping process drapes the wire-frame description onto the simplified surface and simplifies one or more of the line segments that are draped, the draped line segments being rendered over the simplified surface on the rendering device.